package dp

// https://leetcode-cn.com/problems/jump-game-ii/
// 跳跃到最后一个节点，最少的跳跃次数
// 算法: 贪心算法，一直向后遍历，每次都找能跳到下一个节点更远的位置
// 注意：这题要特别留意边界条件
// 时间复杂度: O(n)
func JumpMinStep(nums []int) int {
	// 排除特殊情况
	if len(nums) == 1 {
		return 0
	} else if nums[0] >= len(nums)-1 {
		return 1
	}

	currentPos := 0
	currentTotalStep := 0
	for currentPos < len(nums)-1 {
		// log.Printf("current pos: %d, can jump step: %d\n", currentPos, nums[currentPos])
		// 如果当前节点能直接跳到最后一个节点，则直接退出循环
		if currentPos+nums[currentPos] >= len(nums)-1 {
			currentTotalStep++
			break
		}
		currentGoalPos := minInt(nums[currentPos]+currentPos, len(nums)-1)
		nextGoalPos := 0
		currentMaxPos := 0
		for index := currentPos + 1; index <= currentGoalPos; index++ {
			currentCanJumpPos := minInt(len(nums)-1, index+nums[index])
			if currentMaxPos < currentCanJumpPos {
				nextGoalPos = index
				currentMaxPos = currentCanJumpPos
			}
		}
		currentPos = nextGoalPos
		currentTotalStep++
	}

	// 因为题干强调了一定可到达，所以这里直接返回即可
	return currentTotalStep
}

// func minInt(a, b int) int {
// 	if a < b {
// 		return a
// 	}
// 	return b
// }
